/*
 * @lc app=leetcode.cn id=86 lang=cpp
 *
 * [86] 分隔链表
 */
#include <iostream>
#include <queue>
#include <stack>

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
int num = 0;
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *partition(ListNode *head, int x)
    {
        /* 一大一小两个子链表，分别记录小于x和大于x的子链表，最后再将二者结合 */
        ListNode *small = new ListNode;
        ListNode *large = new ListNode;
        ListNode *small_head = small;
        ListNode *large_head = large;

        while (head) {
            if (head->val < x) {
                small_head->next = head;
                small_head = head;
            } else {
                large_head->next = head;
                large_head = head;
            }
            head = head->next;
        }
        large_head->next = nullptr;
        small_head->next = large->next;
        return small->next;
    }
};
// @lc code=end

int main()
{
    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    node1->next = node2;
    node2->next = nullptr;
    Solution sol;
    sol.partition(node1, 3);
    return 0;
}
